package backtracking;

import java.util.List;

public class ShoppingOffers638 {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {

        return backtracing(price, special, needs, 0);
    }

    private int backtracing(List<Integer> price, List<List<Integer>> special, List<Integer> needs, int specialIndex) {
        //没有需要的了，返回
        if (needs.stream().allMatch((o) -> o == 0)) {
            return 0;
        }
        //大礼包全匹配完了，剩下的单件计算
        if (specialIndex >= special.size()) {
            int cost = 0;
            for (int i = 0; i < needs.size(); i++) {
                cost += needs.get(i) * price.get(i);
            }
            return cost;
        }
        //选用大礼包匹配
        List<Integer> specialList = special.get(specialIndex);

        //如果大礼包中数量>需要数量，推进到下一个大礼包
        for (int i = 0; i < needs.size(); i++) {
            if (needs.get(i) < specialList.get(i)) {
                return  backtracing(price, special, needs, specialIndex + 1);
            }
        }

        //不选用这个大礼包，直接到下一个
        int minCost =  backtracing(price, special, needs, specialIndex + 1);

        //大礼包+1，选用该大礼包
        for (int i = 0; i < needs.size(); i++) {
            needs.set(i, needs.get(i) - specialList.get(i));
        }
        int cost2 = specialList.get(specialList.size() - 1) + backtracing(price, special, needs, specialIndex);
        for (int i = 0; i < needs.size(); i++) {
            needs.set(i, needs.get(i) + specialList.get(i));
        }
        return Math.min(minCost,cost2);
    }
}
